#include <bits/stdc++.h>
using namespace std;
int main() {
    int q,k;
    long long n;
    cin >> q;
    while(q--) {
        cin >> n >> k;
        long long a=2;
        long long temp=0;
        long long temp_ans=1;
        while (n!=1&&a<=static_cast<long long>(sqrt(n))) {
            while (n%a==0) {
                n/=a;
                temp++;
            }
            if (temp>=k) {
                temp_ans*=static_cast<long long>(pow(a,temp));
            }
            temp=0;
            a++;
        }
        cout << temp_ans << endl;
    }
    return 0;
}